/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-03-29 09:35:07
 * @LastEditors: lily
 * @LastEditTime: 2021-03-29 13:14:58
 */
/*
 * @lc app=leetcode.cn id=5 lang=javascript
 *
 * [5] 最长回文子串
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    let n = s.length;
    let res = '';
    // 创建 n*n 的二维数组 array(arrObj,mapFn) 将arrObj里的每一个元素执行mapFn
    let dp = Array.from(new Array(n), () => new Array(n).fill(0));
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            // 最后的元素和最前面的元素对比 如不一样就是false
            // 一样则继续向中间比对，中间是否是回文看已经计算过的dp[i + 1][j - 1]
            // j - i < 2 为初始值 即字串长度为1或2时的情况
            dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]);
            // 当新得到的字串长度比之前长时 进行替换
            if (dp[i][j] && j - i + 1 > res.length) {
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;

};


// @lc code=end




// var longestPalindrome = function (s) {

//     let dp = [], res, length = 0
//     for (let i = 0; i < s.length; i++) {
//         let curr = []
//         dp.push(curr)
//         for (let j = i; j < s.length; j++) {
//             let substr = s.substring(i, j + 1)
//             curr.push(substr)
//             dp[i][j - i] = isPalindrome(substr) ? substr : dp[i][j - 1 - i]
//         }
//     }

//     for (let i = 0; i < s.length; i++) {
//         if (dp[i][s.length - i - 1].length > length) {
//             length = dp[i][s.length - i - 1].length
//             res = dp[i][s.length - i - 1]
//         }
//     }
//     return res
// };

// var isPalindrome = function (s) {
//     let newS = s.replace(/[^a-zA-Z0-9]/ig, '').toLowerCase();
//     return newS === newS.split('').reverse().join('')
// };


console.log(longestPalindrome("babad"));